package br.edu.ufcg.splab.techniques.reduction.functions.similarity;

import java.io.IOException;
import java.util.zip.Deflater;

import br.edu.ufcg.splab.generator.TestCase;

/**
 * This function returns the distance of two test cases using text compression.
 * 
 * Normalised Compression Distance (NCD) is defined as follows NCD(x, y) =
 * (C(xy) - min(C(X), C(y)) / max(C(x), C(y)) where C(x) is the size of string x
 * after compression (and C(y) similarly) and C(xy) is the size, after
 * compression, of the string that comprises y concatenated to the end of x.
 * 
 * See the following paper
 * <pre>
 * inproceedings{Li03, author = "M. Li and X. Chen and X. Li and B. Ma and P.
 *                      Vitanyi", title = "The Similarity Metric", booktitle =
 *                      {Procs.\ of the 14th Annual ACM-SIAM Symposium on
 *                      Discrete Algorithms}, pages = {863--872}, address =
 *                      {Baltimore, Maryland}, year = "2003", }
 * </pre>
 * Note that NCD is not a distance metric. It is NOT in general the case that
 * NCD(x, y) = 0 iff x = y NCD(x, y) = NCD(y, x) NCD(x, y) + NCD(y, z) >= NCD(x,
 * z) Do not use this measure in any application that requires metric
 * properties.
 * 
 * Values of NCD will lies in the range [0.0, 1.0 + e] where e is some small
 * value.
 * 
 * We convert to a distance measure by returning min(NCD(x, y), 1.0).
 * 
 */
public class NormalisedCompressionDistance implements DistanceFunction{

	public double getSimilarity(TestCase path1, TestCase path2){
		return compare(path1, path2);
	}
		
	/**
	 * Applies the distance function.
	 * 
	 * @param path1
	 * @param path2
	 * @return the similarity value.
	 */
	private double compare(TestCase path1, TestCase path2) {
		double ncd = 0.00;
		try {
			ncd = Math.min(ncd(path1, path2), 1.0);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return ncd;
	}
	
	/**
	 * Applies the normalised compression distance.
	 * 
	 * @param x
	 * @param y
	 * @return
	 * @throws IOException 
	 */
	private double ncd(TestCase first, TestCase second) throws IOException {
		String concatenatedStrings = first.toString() + second.toString();
		double num = zlibBytes(concatenatedStrings) - Math.min(zlibBytes(first.toString()), zlibBytes(second.toString()));
		double den = Math.max(zlibBytes(first.toString()), zlibBytes(second.toString()));
		
		return num/den;
	}
	
	/**
	 * Defines a function for returning the size of an object (in this case, a String) after 
	 * compression (in this case, by GZip).
	 * @param object
	 * @return
	 * @throws IOException
	 */
	private static int zlibBytes(String object) throws IOException{
		byte[] objectBytes = object.getBytes();
		Deflater deflater = new Deflater();
		deflater.setInput(objectBytes);
		deflater.finish();
		byte[] out = new byte[100000];
		int size = deflater.deflate(out);
		return size;
	}
	
	/**
     * Provide a string representation of the similarity function to be written.
     * @return The string representation of the similarity function.
     */
	public String getFunctionName(){
		return "NCD";
	}
	
}
